{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "379b06b9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "start\tground\tground\tground\tground\tground\tground\tground\tground\tground\tground\tground\t\n",
      "ground\tground\tground\tground\tground\ttrap\tground\tground\tground\tground\tground\tground\t\n",
      "ground\tground\ttrap\tground\ttrap\tground\tground\tground\tground\tground\tground\tground\t\n",
      "ground\tground\tground\tground\tground\tground\tground\ttrap\tground\tground\tground\tground\t\n",
      "ground\tground\tground\ttrap\tground\tground\tground\tground\tground\tground\tground\tground\t\n",
      "ground\ttrap\tground\tground\tground\tground\tground\tground\tground\tground\tground\tground\t\n",
      "ground\tground\tground\tground\tground\tground\tground\tground\tground\tground\tground\tground\t\n",
      "ground\tground\tground\tground\tground\tground\ttrap\tground\tground\tground\tground\tground\t\n",
      "ground\tground\tground\tground\tground\tground\tground\tground\ttrap\tground\tground\tground\t\n",
      "ground\tground\tground\tground\ttrap\tground\tground\tground\tground\tground\tground\tground\t\n",
      "ground\tground\tground\tground\tground\tground\tground\tground\tground\ttrap\tground\tground\t\n",
      "ground\tground\tground\tground\tground\tground\tground\tground\tground\tground\tground\tterminal\t\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "\n",
    "\n",
    "ROWS, COLS, ACTIONS = 12, 12, {0:'up', 1:'down', 2:'left', 3:'right'}\n",
    "NUM_ACTIONS = len(ACTIONS)\n",
    "GAMMA = 0.9 # 折扣因子\n",
    "\n",
    "epoch = 1500\n",
    "# 价值函数初始化\n",
    "values = np.zeros((ROWS, COLS))\n",
    "policy = np.zeros((ROWS, COLS), dtype=int)  # 初始化策略为随机策略\n",
    "\n",
    "\n",
    "def get_state(row, col):\n",
    "    \"\"\"\n",
    "    初始化环境的状态，输出当且格子的状态\n",
    "    \"\"\"\n",
    "\n",
    "    # 如果要改地图大小，请修改这里\n",
    "    if (row, col) in [(0, 0)]:\n",
    "        return 'start'\n",
    "    if (row, col) in [(11, 11)]:\n",
    "        return 'terminal'\n",
    "    if (row, col) in [(1, 5), (2, 2), (2, 4), (3, 7), (4, 3), (5, 1), (7, 6), (8, 8), (9, 4), (10, 9)]:\n",
    "        return 'trap'\n",
    "    return 'ground'\n",
    "\n",
    "# 环境状态可视化\n",
    "for r in range(ROWS):\n",
    "    for c in range(COLS):\n",
    "        print(get_state(r, c), end='\\t')\n",
    "    print()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "1be2d2db",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0 (0, 0, -1)\t0 0 1 (1, 0, -1)\t0 0 2 (0, 0, -1)\t0 0 3 (0, 1, -1)\t\n",
      "0 1 0 (0, 1, -1)\t0 1 1 (1, 1, -1)\t0 1 2 (0, 0, -1)\t0 1 3 (0, 2, -1)\t\n",
      "0 2 0 (0, 2, -1)\t0 2 1 (1, 2, -1)\t0 2 2 (0, 1, -1)\t0 2 3 (0, 3, -1)\t\n",
      "0 3 0 (0, 3, -1)\t0 3 1 (1, 3, -1)\t0 3 2 (0, 2, -1)\t0 3 3 (0, 4, -1)\t\n",
      "0 4 0 (0, 4, -1)\t0 4 1 (1, 4, -1)\t0 4 2 (0, 3, -1)\t0 4 3 (0, 5, -1)\t\n",
      "0 5 0 (0, 5, -1)\t0 5 1 (1, 5, -100)\t0 5 2 (0, 4, -1)\t0 5 3 (0, 6, -1)\t\n",
      "0 6 0 (0, 6, -1)\t0 6 1 (1, 6, -1)\t0 6 2 (0, 5, -1)\t0 6 3 (0, 7, -1)\t\n",
      "0 7 0 (0, 7, -1)\t0 7 1 (1, 7, -1)\t0 7 2 (0, 6, -1)\t0 7 3 (0, 8, -1)\t\n",
      "0 8 0 (0, 8, -1)\t0 8 1 (1, 8, -1)\t0 8 2 (0, 7, -1)\t0 8 3 (0, 9, -1)\t\n",
      "0 9 0 (0, 9, -1)\t0 9 1 (1, 9, -1)\t0 9 2 (0, 8, -1)\t0 9 3 (0, 10, -1)\t\n",
      "0 10 0 (0, 10, -1)\t0 10 1 (1, 10, -1)\t0 10 2 (0, 9, -1)\t0 10 3 (0, 11, -1)\t\n",
      "0 11 0 (0, 11, -1)\t0 11 1 (1, 11, -1)\t0 11 2 (0, 10, -1)\t0 11 3 (0, 11, -1)\t\n",
      "1 0 0 (0, 0, -1)\t1 0 1 (2, 0, -1)\t1 0 2 (1, 0, -1)\t1 0 3 (1, 1, -1)\t\n",
      "1 1 0 (0, 1, -1)\t1 1 1 (2, 1, -1)\t1 1 2 (1, 0, -1)\t1 1 3 (1, 2, -1)\t\n",
      "1 2 0 (0, 2, -1)\t1 2 1 (2, 2, -100)\t1 2 2 (1, 1, -1)\t1 2 3 (1, 3, -1)\t\n",
      "1 3 0 (0, 3, -1)\t1 3 1 (2, 3, -1)\t1 3 2 (1, 2, -1)\t1 3 3 (1, 4, -1)\t\n",
      "1 4 0 (0, 4, -1)\t1 4 1 (2, 4, -100)\t1 4 2 (1, 3, -1)\t1 4 3 (1, 5, -100)\t\n",
      "1 5 0 (1, 5, 0)\t1 5 1 (1, 5, 0)\t1 5 2 (1, 5, 0)\t1 5 3 (1, 5, 0)\t\n",
      "1 6 0 (0, 6, -1)\t1 6 1 (2, 6, -1)\t1 6 2 (1, 5, -100)\t1 6 3 (1, 7, -1)\t\n",
      "1 7 0 (0, 7, -1)\t1 7 1 (2, 7, -1)\t1 7 2 (1, 6, -1)\t1 7 3 (1, 8, -1)\t\n",
      "1 8 0 (0, 8, -1)\t1 8 1 (2, 8, -1)\t1 8 2 (1, 7, -1)\t1 8 3 (1, 9, -1)\t\n",
      "1 9 0 (0, 9, -1)\t1 9 1 (2, 9, -1)\t1 9 2 (1, 8, -1)\t1 9 3 (1, 10, -1)\t\n",
      "1 10 0 (0, 10, -1)\t1 10 1 (2, 10, -1)\t1 10 2 (1, 9, -1)\t1 10 3 (1, 11, -1)\t\n",
      "1 11 0 (0, 11, -1)\t1 11 1 (2, 11, -1)\t1 11 2 (1, 10, -1)\t1 11 3 (1, 11, -1)\t\n",
      "2 0 0 (1, 0, -1)\t2 0 1 (3, 0, -1)\t2 0 2 (2, 0, -1)\t2 0 3 (2, 1, -1)\t\n",
      "2 1 0 (1, 1, -1)\t2 1 1 (3, 1, -1)\t2 1 2 (2, 0, -1)\t2 1 3 (2, 2, -100)\t\n",
      "2 2 0 (2, 2, 0)\t2 2 1 (2, 2, 0)\t2 2 2 (2, 2, 0)\t2 2 3 (2, 2, 0)\t\n",
      "2 3 0 (1, 3, -1)\t2 3 1 (3, 3, -1)\t2 3 2 (2, 2, -100)\t2 3 3 (2, 4, -100)\t\n",
      "2 4 0 (2, 4, 0)\t2 4 1 (2, 4, 0)\t2 4 2 (2, 4, 0)\t2 4 3 (2, 4, 0)\t\n",
      "2 5 0 (1, 5, -100)\t2 5 1 (3, 5, -1)\t2 5 2 (2, 4, -100)\t2 5 3 (2, 6, -1)\t\n",
      "2 6 0 (1, 6, -1)\t2 6 1 (3, 6, -1)\t2 6 2 (2, 5, -1)\t2 6 3 (2, 7, -1)\t\n",
      "2 7 0 (1, 7, -1)\t2 7 1 (3, 7, -100)\t2 7 2 (2, 6, -1)\t2 7 3 (2, 8, -1)\t\n",
      "2 8 0 (1, 8, -1)\t2 8 1 (3, 8, -1)\t2 8 2 (2, 7, -1)\t2 8 3 (2, 9, -1)\t\n",
      "2 9 0 (1, 9, -1)\t2 9 1 (3, 9, -1)\t2 9 2 (2, 8, -1)\t2 9 3 (2, 10, -1)\t\n",
      "2 10 0 (1, 10, -1)\t2 10 1 (3, 10, -1)\t2 10 2 (2, 9, -1)\t2 10 3 (2, 11, -1)\t\n",
      "2 11 0 (1, 11, -1)\t2 11 1 (3, 11, -1)\t2 11 2 (2, 10, -1)\t2 11 3 (2, 11, -1)\t\n",
      "3 0 0 (2, 0, -1)\t3 0 1 (4, 0, -1)\t3 0 2 (3, 0, -1)\t3 0 3 (3, 1, -1)\t\n",
      "3 1 0 (2, 1, -1)\t3 1 1 (4, 1, -1)\t3 1 2 (3, 0, -1)\t3 1 3 (3, 2, -1)\t\n",
      "3 2 0 (2, 2, -100)\t3 2 1 (4, 2, -1)\t3 2 2 (3, 1, -1)\t3 2 3 (3, 3, -1)\t\n",
      "3 3 0 (2, 3, -1)\t3 3 1 (4, 3, -100)\t3 3 2 (3, 2, -1)\t3 3 3 (3, 4, -1)\t\n",
      "3 4 0 (2, 4, -100)\t3 4 1 (4, 4, -1)\t3 4 2 (3, 3, -1)\t3 4 3 (3, 5, -1)\t\n",
      "3 5 0 (2, 5, -1)\t3 5 1 (4, 5, -1)\t3 5 2 (3, 4, -1)\t3 5 3 (3, 6, -1)\t\n",
      "3 6 0 (2, 6, -1)\t3 6 1 (4, 6, -1)\t3 6 2 (3, 5, -1)\t3 6 3 (3, 7, -100)\t\n",
      "3 7 0 (3, 7, 0)\t3 7 1 (3, 7, 0)\t3 7 2 (3, 7, 0)\t3 7 3 (3, 7, 0)\t\n",
      "3 8 0 (2, 8, -1)\t3 8 1 (4, 8, -1)\t3 8 2 (3, 7, -100)\t3 8 3 (3, 9, -1)\t\n",
      "3 9 0 (2, 9, -1)\t3 9 1 (4, 9, -1)\t3 9 2 (3, 8, -1)\t3 9 3 (3, 10, -1)\t\n",
      "3 10 0 (2, 10, -1)\t3 10 1 (4, 10, -1)\t3 10 2 (3, 9, -1)\t3 10 3 (3, 11, -1)\t\n",
      "3 11 0 (2, 11, -1)\t3 11 1 (4, 11, -1)\t3 11 2 (3, 10, -1)\t3 11 3 (3, 11, -1)\t\n",
      "4 0 0 (3, 0, -1)\t4 0 1 (5, 0, -1)\t4 0 2 (4, 0, -1)\t4 0 3 (4, 1, -1)\t\n",
      "4 1 0 (3, 1, -1)\t4 1 1 (5, 1, -100)\t4 1 2 (4, 0, -1)\t4 1 3 (4, 2, -1)\t\n",
      "4 2 0 (3, 2, -1)\t4 2 1 (5, 2, -1)\t4 2 2 (4, 1, -1)\t4 2 3 (4, 3, -100)\t\n",
      "4 3 0 (4, 3, 0)\t4 3 1 (4, 3, 0)\t4 3 2 (4, 3, 0)\t4 3 3 (4, 3, 0)\t\n",
      "4 4 0 (3, 4, -1)\t4 4 1 (5, 4, -1)\t4 4 2 (4, 3, -100)\t4 4 3 (4, 5, -1)\t\n",
      "4 5 0 (3, 5, -1)\t4 5 1 (5, 5, -1)\t4 5 2 (4, 4, -1)\t4 5 3 (4, 6, -1)\t\n",
      "4 6 0 (3, 6, -1)\t4 6 1 (5, 6, -1)\t4 6 2 (4, 5, -1)\t4 6 3 (4, 7, -1)\t\n",
      "4 7 0 (3, 7, -100)\t4 7 1 (5, 7, -1)\t4 7 2 (4, 6, -1)\t4 7 3 (4, 8, -1)\t\n",
      "4 8 0 (3, 8, -1)\t4 8 1 (5, 8, -1)\t4 8 2 (4, 7, -1)\t4 8 3 (4, 9, -1)\t\n",
      "4 9 0 (3, 9, -1)\t4 9 1 (5, 9, -1)\t4 9 2 (4, 8, -1)\t4 9 3 (4, 10, -1)\t\n",
      "4 10 0 (3, 10, -1)\t4 10 1 (5, 10, -1)\t4 10 2 (4, 9, -1)\t4 10 3 (4, 11, -1)\t\n",
      "4 11 0 (3, 11, -1)\t4 11 1 (5, 11, -1)\t4 11 2 (4, 10, -1)\t4 11 3 (4, 11, -1)\t\n",
      "5 0 0 (4, 0, -1)\t5 0 1 (6, 0, -1)\t5 0 2 (5, 0, -1)\t5 0 3 (5, 1, -100)\t\n",
      "5 1 0 (5, 1, 0)\t5 1 1 (5, 1, 0)\t5 1 2 (5, 1, 0)\t5 1 3 (5, 1, 0)\t\n",
      "5 2 0 (4, 2, -1)\t5 2 1 (6, 2, -1)\t5 2 2 (5, 1, -100)\t5 2 3 (5, 3, -1)\t\n",
      "5 3 0 (4, 3, -100)\t5 3 1 (6, 3, -1)\t5 3 2 (5, 2, -1)\t5 3 3 (5, 4, -1)\t\n",
      "5 4 0 (4, 4, -1)\t5 4 1 (6, 4, -1)\t5 4 2 (5, 3, -1)\t5 4 3 (5, 5, -1)\t\n",
      "5 5 0 (4, 5, -1)\t5 5 1 (6, 5, -1)\t5 5 2 (5, 4, -1)\t5 5 3 (5, 6, -1)\t\n",
      "5 6 0 (4, 6, -1)\t5 6 1 (6, 6, -1)\t5 6 2 (5, 5, -1)\t5 6 3 (5, 7, -1)\t\n",
      "5 7 0 (4, 7, -1)\t5 7 1 (6, 7, -1)\t5 7 2 (5, 6, -1)\t5 7 3 (5, 8, -1)\t\n",
      "5 8 0 (4, 8, -1)\t5 8 1 (6, 8, -1)\t5 8 2 (5, 7, -1)\t5 8 3 (5, 9, -1)\t\n",
      "5 9 0 (4, 9, -1)\t5 9 1 (6, 9, -1)\t5 9 2 (5, 8, -1)\t5 9 3 (5, 10, -1)\t\n",
      "5 10 0 (4, 10, -1)\t5 10 1 (6, 10, -1)\t5 10 2 (5, 9, -1)\t5 10 3 (5, 11, -1)\t\n",
      "5 11 0 (4, 11, -1)\t5 11 1 (6, 11, -1)\t5 11 2 (5, 10, -1)\t5 11 3 (5, 11, -1)\t\n",
      "6 0 0 (5, 0, -1)\t6 0 1 (7, 0, -1)\t6 0 2 (6, 0, -1)\t6 0 3 (6, 1, -1)\t\n",
      "6 1 0 (5, 1, -100)\t6 1 1 (7, 1, -1)\t6 1 2 (6, 0, -1)\t6 1 3 (6, 2, -1)\t\n",
      "6 2 0 (5, 2, -1)\t6 2 1 (7, 2, -1)\t6 2 2 (6, 1, -1)\t6 2 3 (6, 3, -1)\t\n",
      "6 3 0 (5, 3, -1)\t6 3 1 (7, 3, -1)\t6 3 2 (6, 2, -1)\t6 3 3 (6, 4, -1)\t\n",
      "6 4 0 (5, 4, -1)\t6 4 1 (7, 4, -1)\t6 4 2 (6, 3, -1)\t6 4 3 (6, 5, -1)\t\n",
      "6 5 0 (5, 5, -1)\t6 5 1 (7, 5, -1)\t6 5 2 (6, 4, -1)\t6 5 3 (6, 6, -1)\t\n",
      "6 6 0 (5, 6, -1)\t6 6 1 (7, 6, -100)\t6 6 2 (6, 5, -1)\t6 6 3 (6, 7, -1)\t\n",
      "6 7 0 (5, 7, -1)\t6 7 1 (7, 7, -1)\t6 7 2 (6, 6, -1)\t6 7 3 (6, 8, -1)\t\n",
      "6 8 0 (5, 8, -1)\t6 8 1 (7, 8, -1)\t6 8 2 (6, 7, -1)\t6 8 3 (6, 9, -1)\t\n",
      "6 9 0 (5, 9, -1)\t6 9 1 (7, 9, -1)\t6 9 2 (6, 8, -1)\t6 9 3 (6, 10, -1)\t\n",
      "6 10 0 (5, 10, -1)\t6 10 1 (7, 10, -1)\t6 10 2 (6, 9, -1)\t6 10 3 (6, 11, -1)\t\n",
      "6 11 0 (5, 11, -1)\t6 11 1 (7, 11, -1)\t6 11 2 (6, 10, -1)\t6 11 3 (6, 11, -1)\t\n",
      "7 0 0 (6, 0, -1)\t7 0 1 (8, 0, -1)\t7 0 2 (7, 0, -1)\t7 0 3 (7, 1, -1)\t\n",
      "7 1 0 (6, 1, -1)\t7 1 1 (8, 1, -1)\t7 1 2 (7, 0, -1)\t7 1 3 (7, 2, -1)\t\n",
      "7 2 0 (6, 2, -1)\t7 2 1 (8, 2, -1)\t7 2 2 (7, 1, -1)\t7 2 3 (7, 3, -1)\t\n",
      "7 3 0 (6, 3, -1)\t7 3 1 (8, 3, -1)\t7 3 2 (7, 2, -1)\t7 3 3 (7, 4, -1)\t\n",
      "7 4 0 (6, 4, -1)\t7 4 1 (8, 4, -1)\t7 4 2 (7, 3, -1)\t7 4 3 (7, 5, -1)\t\n",
      "7 5 0 (6, 5, -1)\t7 5 1 (8, 5, -1)\t7 5 2 (7, 4, -1)\t7 5 3 (7, 6, -100)\t\n",
      "7 6 0 (7, 6, 0)\t7 6 1 (7, 6, 0)\t7 6 2 (7, 6, 0)\t7 6 3 (7, 6, 0)\t\n",
      "7 7 0 (6, 7, -1)\t7 7 1 (8, 7, -1)\t7 7 2 (7, 6, -100)\t7 7 3 (7, 8, -1)\t\n",
      "7 8 0 (6, 8, -1)\t7 8 1 (8, 8, -100)\t7 8 2 (7, 7, -1)\t7 8 3 (7, 9, -1)\t\n",
      "7 9 0 (6, 9, -1)\t7 9 1 (8, 9, -1)\t7 9 2 (7, 8, -1)\t7 9 3 (7, 10, -1)\t\n",
      "7 10 0 (6, 10, -1)\t7 10 1 (8, 10, -1)\t7 10 2 (7, 9, -1)\t7 10 3 (7, 11, -1)\t\n",
      "7 11 0 (6, 11, -1)\t7 11 1 (8, 11, -1)\t7 11 2 (7, 10, -1)\t7 11 3 (7, 11, -1)\t\n",
      "8 0 0 (7, 0, -1)\t8 0 1 (9, 0, -1)\t8 0 2 (8, 0, -1)\t8 0 3 (8, 1, -1)\t\n",
      "8 1 0 (7, 1, -1)\t8 1 1 (9, 1, -1)\t8 1 2 (8, 0, -1)\t8 1 3 (8, 2, -1)\t\n",
      "8 2 0 (7, 2, -1)\t8 2 1 (9, 2, -1)\t8 2 2 (8, 1, -1)\t8 2 3 (8, 3, -1)\t\n",
      "8 3 0 (7, 3, -1)\t8 3 1 (9, 3, -1)\t8 3 2 (8, 2, -1)\t8 3 3 (8, 4, -1)\t\n",
      "8 4 0 (7, 4, -1)\t8 4 1 (9, 4, -100)\t8 4 2 (8, 3, -1)\t8 4 3 (8, 5, -1)\t\n",
      "8 5 0 (7, 5, -1)\t8 5 1 (9, 5, -1)\t8 5 2 (8, 4, -1)\t8 5 3 (8, 6, -1)\t\n",
      "8 6 0 (7, 6, -100)\t8 6 1 (9, 6, -1)\t8 6 2 (8, 5, -1)\t8 6 3 (8, 7, -1)\t\n",
      "8 7 0 (7, 7, -1)\t8 7 1 (9, 7, -1)\t8 7 2 (8, 6, -1)\t8 7 3 (8, 8, -100)\t\n",
      "8 8 0 (8, 8, 0)\t8 8 1 (8, 8, 0)\t8 8 2 (8, 8, 0)\t8 8 3 (8, 8, 0)\t\n",
      "8 9 0 (7, 9, -1)\t8 9 1 (9, 9, -1)\t8 9 2 (8, 8, -100)\t8 9 3 (8, 10, -1)\t\n",
      "8 10 0 (7, 10, -1)\t8 10 1 (9, 10, -1)\t8 10 2 (8, 9, -1)\t8 10 3 (8, 11, -1)\t\n",
      "8 11 0 (7, 11, -1)\t8 11 1 (9, 11, -1)\t8 11 2 (8, 10, -1)\t8 11 3 (8, 11, -1)\t\n",
      "9 0 0 (8, 0, -1)\t9 0 1 (10, 0, -1)\t9 0 2 (9, 0, -1)\t9 0 3 (9, 1, -1)\t\n",
      "9 1 0 (8, 1, -1)\t9 1 1 (10, 1, -1)\t9 1 2 (9, 0, -1)\t9 1 3 (9, 2, -1)\t\n",
      "9 2 0 (8, 2, -1)\t9 2 1 (10, 2, -1)\t9 2 2 (9, 1, -1)\t9 2 3 (9, 3, -1)\t\n",
      "9 3 0 (8, 3, -1)\t9 3 1 (10, 3, -1)\t9 3 2 (9, 2, -1)\t9 3 3 (9, 4, -100)\t\n",
      "9 4 0 (9, 4, 0)\t9 4 1 (9, 4, 0)\t9 4 2 (9, 4, 0)\t9 4 3 (9, 4, 0)\t\n",
      "9 5 0 (8, 5, -1)\t9 5 1 (10, 5, -1)\t9 5 2 (9, 4, -100)\t9 5 3 (9, 6, -1)\t\n",
      "9 6 0 (8, 6, -1)\t9 6 1 (10, 6, -1)\t9 6 2 (9, 5, -1)\t9 6 3 (9, 7, -1)\t\n",
      "9 7 0 (8, 7, -1)\t9 7 1 (10, 7, -1)\t9 7 2 (9, 6, -1)\t9 7 3 (9, 8, -1)\t\n",
      "9 8 0 (8, 8, -100)\t9 8 1 (10, 8, -1)\t9 8 2 (9, 7, -1)\t9 8 3 (9, 9, -1)\t\n",
      "9 9 0 (8, 9, -1)\t9 9 1 (10, 9, -100)\t9 9 2 (9, 8, -1)\t9 9 3 (9, 10, -1)\t\n",
      "9 10 0 (8, 10, -1)\t9 10 1 (10, 10, -1)\t9 10 2 (9, 9, -1)\t9 10 3 (9, 11, -1)\t\n",
      "9 11 0 (8, 11, -1)\t9 11 1 (10, 11, -1)\t9 11 2 (9, 10, -1)\t9 11 3 (9, 11, -1)\t\n",
      "10 0 0 (9, 0, -1)\t10 0 1 (11, 0, -1)\t10 0 2 (10, 0, -1)\t10 0 3 (10, 1, -1)\t\n",
      "10 1 0 (9, 1, -1)\t10 1 1 (11, 1, -1)\t10 1 2 (10, 0, -1)\t10 1 3 (10, 2, -1)\t\n",
      "10 2 0 (9, 2, -1)\t10 2 1 (11, 2, -1)\t10 2 2 (10, 1, -1)\t10 2 3 (10, 3, -1)\t\n",
      "10 3 0 (9, 3, -1)\t10 3 1 (11, 3, -1)\t10 3 2 (10, 2, -1)\t10 3 3 (10, 4, -1)\t\n",
      "10 4 0 (9, 4, -100)\t10 4 1 (11, 4, -1)\t10 4 2 (10, 3, -1)\t10 4 3 (10, 5, -1)\t\n",
      "10 5 0 (9, 5, -1)\t10 5 1 (11, 5, -1)\t10 5 2 (10, 4, -1)\t10 5 3 (10, 6, -1)\t\n",
      "10 6 0 (9, 6, -1)\t10 6 1 (11, 6, -1)\t10 6 2 (10, 5, -1)\t10 6 3 (10, 7, -1)\t\n",
      "10 7 0 (9, 7, -1)\t10 7 1 (11, 7, -1)\t10 7 2 (10, 6, -1)\t10 7 3 (10, 8, -1)\t\n",
      "10 8 0 (9, 8, -1)\t10 8 1 (11, 8, -1)\t10 8 2 (10, 7, -1)\t10 8 3 (10, 9, -100)\t\n",
      "10 9 0 (10, 9, 0)\t10 9 1 (10, 9, 0)\t10 9 2 (10, 9, 0)\t10 9 3 (10, 9, 0)\t\n",
      "10 10 0 (9, 10, -1)\t10 10 1 (11, 10, -1)\t10 10 2 (10, 9, -100)\t10 10 3 (10, 11, -1)\t\n",
      "10 11 0 (9, 11, -1)\t10 11 1 (11, 11, 100)\t10 11 2 (10, 10, -1)\t10 11 3 (10, 11, -1)\t\n",
      "11 0 0 (10, 0, -1)\t11 0 1 (11, 0, -1)\t11 0 2 (11, 0, -1)\t11 0 3 (11, 1, -1)\t\n",
      "11 1 0 (10, 1, -1)\t11 1 1 (11, 1, -1)\t11 1 2 (11, 0, -1)\t11 1 3 (11, 2, -1)\t\n",
      "11 2 0 (10, 2, -1)\t11 2 1 (11, 2, -1)\t11 2 2 (11, 1, -1)\t11 2 3 (11, 3, -1)\t\n",
      "11 3 0 (10, 3, -1)\t11 3 1 (11, 3, -1)\t11 3 2 (11, 2, -1)\t11 3 3 (11, 4, -1)\t\n",
      "11 4 0 (10, 4, -1)\t11 4 1 (11, 4, -1)\t11 4 2 (11, 3, -1)\t11 4 3 (11, 5, -1)\t\n",
      "11 5 0 (10, 5, -1)\t11 5 1 (11, 5, -1)\t11 5 2 (11, 4, -1)\t11 5 3 (11, 6, -1)\t\n",
      "11 6 0 (10, 6, -1)\t11 6 1 (11, 6, -1)\t11 6 2 (11, 5, -1)\t11 6 3 (11, 7, -1)\t\n",
      "11 7 0 (10, 7, -1)\t11 7 1 (11, 7, -1)\t11 7 2 (11, 6, -1)\t11 7 3 (11, 8, -1)\t\n",
      "11 8 0 (10, 8, -1)\t11 8 1 (11, 8, -1)\t11 8 2 (11, 7, -1)\t11 8 3 (11, 9, -1)\t\n",
      "11 9 0 (10, 9, -100)\t11 9 1 (11, 9, -1)\t11 9 2 (11, 8, -1)\t11 9 3 (11, 10, -1)\t\n",
      "11 10 0 (10, 10, -1)\t11 10 1 (11, 10, -1)\t11 10 2 (11, 9, -1)\t11 10 3 (11, 11, 100)\t\n",
      "11 11 0 (11, 11, 0)\t11 11 1 (11, 11, 0)\t11 11 2 (11, 11, 0)\t11 11 3 (11, 11, 0)\t\n"
     ]
    }
   ],
   "source": [
    "def move(row, col, action):\n",
    "    \"\"\"\n",
    "    移动智能体，根据当前位置和动作，返回新的位置和奖励\n",
    "\n",
    "    状态 & 策略 初始化\n",
    "    \"\"\"\n",
    "    # 结束状态\n",
    "    if get_state(row, col) in ['trap', 'terminal']:\n",
    "        return row, col, 0\n",
    "    \n",
    "    # 移动实现\n",
    "    if action == 'up': row -= 1\n",
    "    elif action == 'down': row += 1\n",
    "    elif action == 'left': col -= 1\n",
    "    elif action == 'right': col += 1\n",
    "\n",
    "    # 边界限制\n",
    "    row = min(max(row, 0), 11)\n",
    "    col = min(max(col, 0), 11)\n",
    "\n",
    "    # 默认奖励为-1，促使智能体尽快到达终点\n",
    "    reward = -1\n",
    "\n",
    "     # 事件处理\n",
    "    state = get_state(row, col)\n",
    "    if state == 'trap': reward = -100\n",
    "    elif state == 'terminal': reward = 100\n",
    "\n",
    "    return row, col, reward\n",
    "\n",
    "# 测试\n",
    "for r in range(ROWS):\n",
    "    for c in range(COLS):\n",
    "        for a in range(NUM_ACTIONS):\n",
    "            print(r, c, a, move(r, c, ACTIONS[a]), end='\\t')\n",
    "        print()\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "cd14c048",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(12, 12, 4)\n",
      "0\n",
      "-0.1\n"
     ]
    }
   ],
   "source": [
    "Q = np.zeros((ROWS, COLS, NUM_ACTIONS))\n",
    "print(Q.shape)\n",
    "\n",
    "def get_action(row, col):\n",
    "    \"\"\"\n",
    "    根据状态选择一个动作\n",
    "    \"\"\"\n",
    "    if random.random() < 0.1: # 有小概率选择随机动作\n",
    "        return random.choice(list(ACTIONS.keys()))\n",
    "    \n",
    "    # 否则选择分数最高的动作\n",
    "    return Q[row, col].argmax()\n",
    "\n",
    "print(get_action(0, 0))\n",
    "\n",
    "def get_update(row, col, action, reward, next_row, next_col, next_action):\n",
    "    \"\"\"\n",
    "    计算更新值\n",
    "    \"\"\"\n",
    "    # 计算目标值\n",
    "    target = reward + GAMMA * Q[next_row, next_col, next_action]\n",
    "    # 计算当前状态-动作对应的Q值\n",
    "    current = Q[row, col, action]\n",
    "    # 根据时序差分算法，当前state，action的分数 = 下个state，action的分数 + 折扣因子 * (目标值 - 当前state，action的分数)\n",
    "    update = current + 0.1 * (target - current) # 0.1是学习率\n",
    "    return update\n",
    "\n",
    "# 在0，0位置向右走，得到-1，到达0.1，再次执行向右走\n",
    "print(get_update(0, 0, 3, -1, 0, 1, 3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "9bb714b7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -139\n",
      "50 -260\n",
      "100 -17\n",
      "150 51\n",
      "200 -8\n",
      "250 -200\n",
      "300 71\n",
      "350 72\n",
      "400 78\n",
      "450 76\n",
      "500 78\n",
      "550 78\n",
      "600 76\n",
      "650 75\n",
      "700 79\n",
      "750 79\n",
      "800 79\n",
      "850 72\n",
      "900 -179\n",
      "950 77\n",
      "1000 76\n",
      "1050 -120\n",
      "1100 79\n",
      "1150 75\n",
      "1200 79\n",
      "1250 77\n",
      "1300 79\n",
      "1350 79\n",
      "1400 -172\n",
      "1450 -138510\n"
     ]
    }
   ],
   "source": [
    "# 策略迭代\n",
    "for epo in range(epoch):\n",
    "    \"\"\"\n",
    "    Sarsa算法\n",
    "    \"\"\"\n",
    "    # 初始化状态 - 从起点开始\n",
    "    row, col = 0, 0\n",
    "\n",
    "    # 随机初始化第一个动作\n",
    "    action = get_action(row, col)\n",
    "\n",
    "    # 计算反馈的和\n",
    "    reward_sum = 0\n",
    "\n",
    "    # 循环直到到达终点或者掉进陷阱\n",
    "    while get_state(row, col) not in ['trap', 'terminal']:\n",
    "        # 执行动作\n",
    "        next_row, next_col, reward = move(row, col, ACTIONS[action])  # 注意这里需要将action index转换为action name\n",
    "        reward_sum += reward\n",
    "\n",
    "        # 求新位置的动作\n",
    "        next_action = get_action(next_row, next_col)\n",
    "\n",
    "        # 更新分数\n",
    "        update = get_update(row, col, action, reward, next_row, next_col, next_action)\n",
    "        Q[row, col, action] = update  # 直接赋值而不是累加\n",
    "\n",
    "        # 更新当前位置\n",
    "        row = next_row\n",
    "        col = next_col\n",
    "        action = next_action\n",
    "\n",
    "    if epo % 50 == 0:\n",
    "        print(epo, reward_sum)\n",
    "\n",
    "# 训练完成后，从Q表中提取最优策略\n",
    "for r in range(ROWS):\n",
    "    for c in range(COLS):\n",
    "        policy[r, c] = Q[r, c].argmax()  # 选择Q值最大的动作作为最优策略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "4f360602",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " S ← ← ↑ ← → → ← ↓ ← → ← \n",
      " ↓ ↑ → ↑ ↑ C ↑ → ↓ ↓ ↓ ↑ \n",
      " ↓ ↓ C ↑ C ↓ ↑ → → ↓ ↓ ← \n",
      " ↓ ← → ↑ ↓ ↓ ↓ C ↓ ↓ ↓ ← \n",
      " ↓ ← ↓ C ↑ ↓ ↓ ↓ ↓ ↓ ↓ ↓ \n",
      " ↓ C ↑ → → → → → ↓ ↓ ↓ ↓ \n",
      " ↓ ↓ → → → → → → → ↓ ↓ ← \n",
      " ↓ ↓ ↓ ↓ ↑ ↑ C → → → ↓ ↓ \n",
      " → ↓ ↓ ↓ ↑ ↓ ↓ ↓ C → ↓ ↓ \n",
      " → → ↓ ↓ C ↓ → → → → ↓ ↓ \n",
      " → → → ↓ → ↓ → ↓ ↓ C ↓ ↓ \n",
      " → → → → → → → → → → → G \n"
     ]
    }
   ],
   "source": [
    "def show_policy(policy):\n",
    "    \"\"\"\n",
    "    可视化策略\n",
    "    \"\"\"\n",
    "    symbols = ['↑','↓','←','→']\n",
    "\n",
    "    for r in range(ROWS):\n",
    "        line = ' '\n",
    "        for c in range(COLS):\n",
    "            s = get_state(r, c)\n",
    "            if s == 'terminal': line += 'G '\n",
    "            elif s == 'trap': line += 'C '\n",
    "            elif (r,c) == (0,0): line += 'S '\n",
    "            else: line += symbols[policy[r,c]] + ' '\n",
    "        print(line)\n",
    "\n",
    "show_policy(policy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "d250d8d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S . . . . . . . . . . . \n",
      ". . . . . T . . . . . . \n",
      ". . T . T . . . . . . . \n",
      ". . . . . . . T . . . . \n",
      ". . . T . . . . . . . . \n",
      ". T . . . . . . . . . . \n",
      ". . . . . . . . . . . . \n",
      ". . . . . . T . . . . . \n",
      ". . . . . . . . T . . . \n",
      ". . . . T . . . . . . . \n",
      ". . . . . . . . . T . . \n",
      ". . . . . . . . . . → G \n",
      "游戏结束！最终状态: terminal\n"
     ]
    }
   ],
   "source": [
    "def show(row, col, action):\n",
    "    # 创建12x12的地图可视化\n",
    "    graph = []\n",
    "    for r in range(ROWS):\n",
    "        for c in range(COLS):\n",
    "            state = get_state(r, c)\n",
    "            if state == 'start':\n",
    "                graph.append('S ')  # 起点\n",
    "            elif state == 'terminal':\n",
    "                graph.append('G ')  # 终点\n",
    "            elif state == 'trap':\n",
    "                graph.append('T ')  # 陷阱\n",
    "            else:\n",
    "                graph.append('. ')  # 普通地面\n",
    "    \n",
    "    # 在当前位置显示动作\n",
    "    symbols = ['↑','↓','←','→']\n",
    "    graph[row * COLS + col] = symbols[action] + ' '\n",
    "    \n",
    "    # 打印地图\n",
    "    graph_str = ''.join(graph)\n",
    "    for i in range(0, ROWS * 2, 2):  # 每行2个字符（符号+空格）\n",
    "        print(graph_str[i*COLS:(i+2)*COLS])\n",
    "\n",
    "import IPython.display as display\n",
    "import time\n",
    "\n",
    "def test():\n",
    "    # 起点\n",
    "    row, col = 0, 0\n",
    "    \n",
    "    # 最多玩N步\n",
    "    for _ in range(200):\n",
    "        # 获取当前状态，如果状态是终点或者掉陷阱则终止\n",
    "        if get_state(row, col) in ['trap', 'terminal']:\n",
    "            print(f\"游戏结束！最终状态: {get_state(row, col)}\")\n",
    "            break\n",
    "            \n",
    "        # 选择最优动作\n",
    "        action = policy[row, col]  # 使用训练好的策略\n",
    "        \n",
    "        display.clear_output(wait=True)\n",
    "        # 添加延时以便观察\n",
    "        time.sleep(0.1)\n",
    "        show(row, col, action)\n",
    "        \n",
    "        # 执行动作\n",
    "        next_row, next_col, reward = move(row, col, ACTIONS[action])\n",
    "        \n",
    "        # 更新位置\n",
    "        row, col = next_row, next_col\n",
    "        \n",
    "        \n",
    "\n",
    "# 运行测试\n",
    "test()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
